package 力扣._42_接雨水;

import java.util.Stack;

public class Solution {
    public int trap(int[] height) {
        //找到各个极小值点

        //依次入栈，若当前元素大于栈顶(极小值)，则出栈直到栈为空或栈顶元素大于等于当前元素，
        //若找到>=极小值的栈顶元素, 这一部分雨水便是  （出栈元素值-极小值）的和
        //否则为0
        //再将雨水高度值（元素值 - 最小值）入栈，出栈个数加1次
        //
        Stack<Integer> stack = new Stack<>();
        int sum = 0;
        for (int i = 0; i < height.length; ) {
            int h = height[i];
            if (stack.isEmpty()) {
                stack.push(h);
                i++;
            } else {
                if (stack.peek() < h) {
                    int min = stack.pop();
                    int count = 1, may_sum = h - min;
                    while (!stack.isEmpty() && stack.peek() <= min) {
                        int pop = stack.pop();
                        count++;
                        may_sum += h - min;  //以右侧高度计算雨水容量，但左侧不一定存在
                    }
                    if (stack.isEmpty()) {
                        //左侧不存在挡板，该区间无法积累雨水，故将入栈备用
                        for (int k = 0; k < count + 1; k++) {
                            stack.push(h);
                        }
                        i++;
                    } else {
                        int l_h = stack.peek(); //左侧挡板高度
                        if (l_h >= h)
                            sum += may_sum;
                        else {
                            may_sum -= count * (h - l_h);//减去多加的雨水
                            sum += may_sum;
                        }
                        int t = Math.min(l_h, h);    //填充高度
                        for (int k = 0; k < count; k++) {
                            stack.push(t);
                        }
                    }
                } else {
                    stack.push(h);
                    i++;
                }
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] h = new int[]{4,2,0,3,2,5};
        int trap = new Solution().trap(h);
        System.out.println(trap);
    }
}
